/**
 * 
 */
package array.passed;

import java.util.List;

/**
 * @author xyyi
 *
 */
public class MedianOfNHostWithNNumber {

	/**
	 * This algorithm to use quick select to partition n integers on each hosts (n hosts) and compute the median of a list of host with n numbers each
	 * 
	 * There are 2 class Host and Server
	 * Host: we can consider host class is a proxy to call a stub object on a physical host.
	 * Time Complexity on each host is O(n) for it is expected time complexity for quick selection
	 * 
	 * Server: this class will compute the median of a list of host with n numbers each
	 * Time Complexity on Server is O(n^2) since all hosts are parallel to run.
	 * 
	 *  The general Time Complexity is O(n^2) 
	 */
	class Host {
		final static int LEFT = 0;
		final static int RIGHT = 1;

		private List<Integer> numbers;
		private int left;
		private int right;
		private int pivot;

		public Host(List<Integer> numbers) {
			left = 0;
			right = numbers.size() - 1;
			this.numbers = numbers;
		}

		public int size() {
			return left > right ? 0 : right - left + 1;
		}

		public int leftSize() {
			return pivot - left;
		}

		public void partition(int pivotValue) {
			if (left > right)
				return;

			int slow = left, fast = left;
			while (fast <= right) {
				if (numbers.get(fast) <= pivotValue) {
					int temp = numbers.get(slow);
					numbers.set(slow, numbers.get(fast));
					numbers.set(fast, temp);
					slow++;
				}
				fast++;
			}

			pivot = slow;
		}

		public boolean hasNumbersLeft() {
			return left <= right;
		}

		int getPivot() {
			return numbers.get(Utilities.getRandom(left, right));
		}

		void updateRange(int direction) {
			if (direction == Host.LEFT) {
				right = pivot - 1;
			} else if (direction == Host.RIGHT) {
				left = pivot;
			}
		}

	}

	class Server {

		public double getMediam(List<Host> hosts) {
			if (hosts == null || hosts.isEmpty())
				throw new IllegalArgumentException("Error message");

			double mediam = 0;
			int totalSize = 0;
			for (Host host : hosts) {
				totalSize += host.size();
			}

			if (totalSize % 2 == 1) {
				mediam = getKth(hosts, totalSize / 2 + 1);
			}
			else {
				mediam = (getKth(hosts, totalSize / 2) + 
						getKth(hosts, totalSize / 2 + 1)) / 2.0;
			}

			return mediam;
		}

		// the kth number of all hosts, k starts form 1
		public int getKth(List<Host> hosts, int k) {
			if (hosts == null || hosts.isEmpty() || k <= 0)
				throw new IllegalArgumentException("Error message");

			int totalSize = 0;
			for (Host host : hosts) {
				totalSize += host.size();
			}
			if (k > totalSize)
				throw new IllegalArgumentException("Error message");

			while (true) {
				int random = Utilities.getRandom(0, hosts.size() - 1);
				int pivotValue = hosts.get(random).getPivot();
				int direction = Host.LEFT;
				int leftSize = 0;

				for (Host host : hosts) { // this should be an async call to each host
					if (host.hasNumbersLeft()) {
						host.partition(pivotValue);
						leftSize += host.leftSize();
					} else {
						hosts.remove(host);
					}
				}

				if (leftSize == k) {
					return pivotValue;
				} else if (leftSize < k) {
					k -= leftSize;
					direction = Host.RIGHT;
				}

				for (Host host : hosts) { // this should be an async call to each host
					host.updateRange(direction);
				}
			}
		}
	}

	public static class Utilities {
		// a random function to return from start to end
		public static int getRandom(int start, int end) {
			assert (start >= 0 && end >= start);
			//TODO to be implemented
			return 0;
		}
	}

	/**
	 * 
	 */
	public MedianOfNHostWithNNumber() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
